/*
    逆元和除法同余、容斥原理

    前置知识
    讲解041 - 同余原理，同余的意义，加减乘同余
    讲解066、讲解067、讲解068、讲解069 - 动态规划基础
    讲解080、讲解081 - 状压dp，题目5需要
    讲解098 - 乘法快速幂，一个数字的n次方怎么算最快

    逆元的意义 & 除法同余
    连续数字逆元的线性递推 & 连续阶乘逆元的线性递推
    容斥原理

    注意：
    讲解097、讲解098、讲解099，可以称为"不用多问为什么"专题
    有兴趣可以翻帖子看证明，用纸和笔跟着推一遍是最好的方式
    因为证明麻烦，并且证明过程没啥扩展性，记住用法和模版即可，当做原子技能使用

    ================================================

    当计算结果比较大时，考试、比赛时经常要求结果对一个数字取余，比如 % 1000000007
    在讲解041中，讲解了加法、减法、乘法如何让中间结果取余
    总的来说：
    加法和乘法，可以让每个中间结果直接取余，最后结果就是正确的
    减法，只需要让每个减完的结果 + MOD，然后 % MOD，最后结果就是正确的

    除法呢？不能这么做，比如下面的例子

    10 / 5，结果对3取余。正确结果是10 / 5得到2，2 % 3得到2
    但是如果中间结果直接取余，10 % 3得到1，5 % 3得到2，(1 / 2) % 3得到0

    会发现结果对不上，这是因为除法同余有比较特别的处理

    也就是除数先转化成逆元，然后让被除数乘以逆元，逆元就是倒数的意思

    ================================================

    如果你想计算：a / b，然后 % MOD结果
    1) 必须保证a/b可以整除，每次有除法的时候，都需要保证绝对能整除
    2) 必须保证MOD是质数，求逆元的原理是费马小定理，要求MOD是质数，比如1000000007
    3) 必须保证b和MOD的最大公约数为1，也就是b和MOD互质

    题目给定的数据一定会满足上面三点，那么就有如下的结论，直接记住，证明略，不用多问为什么
    先求 1/b 的乘法同余数，也就是b的逆元，b的逆元 = b的(MOD-2)次方 % MOD
    然后，(a / b) % MOD的结果，等于，((a % MOD) * (b的逆元)) % MOD的结果

    比如，(10 / 5) % 3，先求5的1次方 % 3 = 2，((10 % 3) * 2) % 3，结果得到2，这是正确的

    你可以假设各种例子，a、b、MOD，但要保证 : a/b能整除、MOD是质数、b和MOD互质

    ================================================

    题目1
    单个除数求逆元
    对数器验证

    时间复杂度O(log MOD)

    ================================================

    直接记住
    不用多问为什么
    连续数字逆元的线性递推
    在 % p意义下，
    1、2、3 . . . n，求每个数的逆元
    用inv[i]，代表i的逆元
    inv[1] = 1
    inv[i] = (int) (p - (long) inv[p % i] * (p / i) % p); // 从左往右线性递推

    道理其实容易理解
    连续阶乘逆元的线性递推
    在 % p意义下，
    1!、2!、3! . . . n!，求每个数的逆元，
    用inv[i]，代表i!的逆元
    先求n!乘法同余的结果，假设为a，然后求a的逆元，假设为b
    inv[n] = b
    inv[i] = ((long) (i + 1) * inv[i + 1]) % MOD; // 从右往左线性递推

    ================================================

    题目2
    连续数字逆元的线性递推
    给定n、p，求1∼n中所有整数在模p意义下的乘法逆元
    1 <= n <= 3 * 10^6
    n < p < 20000528
    输入保证p为质数
    测试链接 : https://www.luogu.com.cn/problem/P3811

    时间复杂度O(n)

    ================================================

    题目3
    连续阶乘逆元的线性递推
    实现组合公式C(n,m)的计算
    最终结果 % 1000000007后返回
    0 <= m <= n <= 1000
    对数器验证

    时间复杂度O(n)

    ================================================

    容斥原理

    道理很简单，课上说明一下

    有关题目可不容易，核心是如何设计出快速查询若干集合交集数量的问答系统，常见的题型有两类
    1）打表查询（题目4、题目5）
    2）不用查询直接公式化简（题目6）

    ================================================

    题目4
    最大公约数为1的子序列数量
    给你一个数组，返回有多少个子序列的最大公约数是1
    结果可能很大对1000000007取模
    测试链接 : https://www.luogu.com.cn/problem/CF803F
    1 <= n <= 10^5
    1 <= nums[i] <= 10^5

    扩展问题 
    最大公约数为k的子序列数量
    给定一个长度为n的正数数组nums，还有正数k
    返回有多少子序列的最大公约数为k

    ================================================

    题目5
    多次查询购买方法
    一共有4种硬币，面值分别为v0、v1、v2、v3，这个永远是确定的
    每次去购物的细节由一个数组arr来表示，每次购物都是一次查询
    arr[0] = 携带v0面值的硬币数量
    arr[1] = 携带v1面值的硬币数量
    arr[2] = 携带v2面值的硬币数量
    arr[3] = 携带v3面值的硬币数量
    arr[4] = 本次购物一定要花多少钱
    返回每次有多少种花钱的方法
    1 <= v0、v1、v2、v3、arr[i] <= 10^5
    查询数量 <= 1000
    测试链接 : https://www.luogu.com.cn/problem/P1450

    本题需要理解
    讲解074 - 完全背包
    讲解080 - 状压dp
    不会的同学看一下

    ================================================

    题目6
    播放列表的数量
    给定三个参数，n、l、k
    你的音乐播放器里有n首不同的歌
    在旅途中你的旅伴想要听l首歌
    听得歌曲不一定不同，即允许歌曲重复
    请你为她按如下两条规则创建一个播放列表
    1) 每首歌至少播放一次
    2) 一首歌只有在其他k首歌播放完之后才能再次播放
    返回可以满足要求的播放列表的数量
    结果可能很大对1000000007取模
    测试链接 : https://leetcode.cn/problems/number-of-music-playlists/

*/